\documentclass[submission]{FPSAC2017}

\articlenumber{26}
\addbibresource{26_Gilmore.bib}

\usepackage{footmisc}
\usepackage{lipsum}
\usepackage{mathrsfs}

\newtheorem{thm}{Theorem}\theoremstyle{plain}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}

\newtheorem*{conj*}{Conjecture}

\def\perm{\operatorname{perm}}
\def\sgn{\operatorname{sgn}}
\theoremstyle{remark}
\newtheorem{rmk}{Remark}



\title{Holey matrimony: marrying two approaches to a tiling problem}

\author[Tomack Gilmore]{Tomack Gilmore\thanks{Research
		supported by the Austrian Science Foundation (FWF), grant F50-N15, in the
		framework of the Special Research Program ``Algorithmic and Enumerative
		Combinatorics''.}}

\address{Fakult\"at f\"ur Mathematik, Universit\"at Wien,
	Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria}

\received{14\textsuperscript{th} November 2016}

\revised{1\textsuperscript{st} April 2017}

\abstract{Consider an hexagonal region on the triangular lattice, the interior of which contains a number of holes. This extended abstract outlines a recent result by the author that marries together two separate approaches to counting tilings in order to express the number of rhombus tilings of a holey hexagon (subject to very mild restrictions) as a determinant whose size is dependent only on the regions that have been removed. The main result follows from explicitly deriving the $(i,j)$-entries of the inverse Kasteleyn matrix corresponding to certain sub-graphs of the hexagonal lattice. This generalises a number of known results and may well lead to a proof of Ciucu's electrostatic conjecture for the most general family of holes to date.}

\keywords{Rhombus tilings, holey hexagons, Kasteleyn matrices, electrostatics.}


\begin{document}

\maketitle

\vspace{-0.4cm}\section{Introduction}\label{sec:Intro}
Let $\mathscr{T}$ denote the triangular lattice consisting of unit equilateral triangles, drawn so that one of the families of lattice lines is vertical. Suppose $H_{a,b,c}$ is the hexagonal sub-region of $\mathscr{T}$ that has sides of length $a,b,c,a,b,c$ (going clock-wise from the south-west side), centred at some origin\footnote{The origin is the intersection of the two lines that intersect the midpoints of two pairs of parallel sides of $H_{a,b,c}$. Each family of lattice lines comprising $\mathscr{T}$ may be labelled with respect to $O$, thus each unit triangle of $\mathscr{T}$ is given by a triple consisting of the labels of the lattice lines that comprise its edges.} $O$. By joining together two unit triangles on $\mathscr{T}$ that share exactly one edge we obtain a unit rhombus, thus a \emph{rhombus tiling} of $H_{a,b,c}$ (from now on referred to as simply a tiling) arises from joining together in this way all pairs of unit triangles contained in $H_{a,b,c}$ (see \cref{fig:PlanPart}).
\begin{figure}
	\centering
	\includegraphics[width=0.75\textwidth]{fig1}
	\caption{From left to right: a plane partition; its three dimensional representation as a pile of unit cubes stacked in the corner of a $3\times4\times5$ box; its two dimensional representation as a tiling of $H_{3,4,5}$; the hexagonal sub-region of $\mathscr{T}$, $H_{3,4,5}$.}
	\label{fig:PlanPart}\vspace{-0.8cm}
\end{figure}

Tilings of hexagons first arose in the literature in 1916 (albeit in a different form), when MacMahon~\cite{MacMahon16} showed that the number of \emph{plane partitions}\footnote{A \emph{plane partition} is a left justified array of positive integers where the row lengths weakly decrease from top to bottom, and the entries are weakly decreasing along rows and down columns.} that fit inside an $a\times b\times c$ box\footnote{ A plane partition fits inside an $a\times b\times c$ box if its row length is at most $a$, its entries are at most $b$, and its column length is at most $c$.} is given by
\vspace{-0.1cm}\begin{equation}
\label{eq:MacBox}PP(a,b,c):=\prod_{i=1}^a\prod_{j=1}^b\prod_{k=1}^c\frac{i+j+k-1}{i+j+k-2}.\vspace{-0.1cm}\end{equation}

Although these objects may at first sight seem completely unrelated to tilings, the bijection that exists between $a\times b\times c$ boxed plane partitions and tilings of $H_{a,b,c}$ is perhaps one of the most beautiful relationships in combinatorics (see \cref{fig:PlanPart}). In the 100 years since their introduction these objects have garnered a great deal of attention and thus the mathematics surrounding them is rich and varied (for an overview of the history of tilings see~\cite{KrattenthalerSTAN} and many of the references therein). 

More recent results in this area have centred on tilings of hexagons that contain defects or punctures within their interior (these are obtained by removing a set $T$ of unit triangles from the interior of $H_{a,b,c}$-- such \emph{holey hexagons} shall be denoted $H_{a,b,c}\setminus T$)\footnote{The set $T$ is a union of \emph{unconnected regions} that are each comprised of \emph{connected} unit triangles, that is, $T:=\cup_{i}T_i$ where $T_i$ is either a single unit triangle or a set of unit triangles in which every $t\in T_i$ intersects with at least one other $t'\in T_i$, $t'\neq t$ either at an edge (forming a rhombus) or a corner (forming a little unit bow-tie), and for any pair of triangles $t\in T_i,t'\in T_j,i\neq j$, $t$ and $t'$ are not connected. Note that any two unit triangles that share an edge with the outer boundary are also deemed to be connected.}. Of course once we begin to remove regions from the interior of $H_{a,b,c}$ the three dimensional interpretation of tilings as piles of unit cubes breaks down and we end up with tilings that are reminiscent of the works of Escher (see \cref{fig:TilG}). Enumerating these types of tilings is generally more complicated, nonetheless in recent years a number of formulas have arisen for different classes of holes (see \cref{fig:HoleTypes} for a small selection of examples of different types of holey hexagons considered so far in the literature).
\begin{figure}
	\centering
	\includegraphics[width=0.75\textwidth]{fig2}
	\caption{Examples of the types of holey hexagons considered by Ciucu and Fischer in~\cite{CiucuFischer12},~\cite{CiucuFischer16}, and the author~\cite{Gilmore16} (from left to right).}
	\label{fig:HoleTypes}
\vspace{-0.8cm}\end{figure}

It is perhaps worth briefly discussing the motivation behind this sort of enumeration. Not only do such problems present a considerable counting challenge, but when considered on a large scale they appear to have an interpretation that comes directly from physics (more specifically, electrostatics). Indeed it has been conjectured by Ciucu~\cite{Ciucu08} that the interaction between holes that are a large distance apart within a sea of dimers (that is, tilings of the plane that contain a set of holes) is governed by a Coulomb-like law\footnote{Coulomb's law states that the force of attraction between two point charges in an electromagnetic field is inversely proportional to the distance between them.}, while in~\cite{Gilmore16} the author showed how a well-known physical principle known as the \emph{method of images} emerges from the asymptotic analysis of formulas that count vertically symmetric tilings of certain holey hexagons.

Although Ciucu's conjecture remains wide open, it is the belief of the author that the main result of this paper (\cref{thm:MainRes}, presented below) could lead to a proof for the most general class of holes to date.

\begin{thm}\label{thm:MainRes}
	Suppose $T=\{l_1,\dots,l_k,r_1,\dots,r_k\}$ is a set of (left, $l_j$, and right, $r_i$, pointing) unit triangles that comprise a union of unconnected regions contained in the interior of $H_{a,b,c}$, where each region has an even charge\footnote{The \emph{charge} is the difference between the right and left pointing unit triangles that comprise a region.} and the sum of the charges is zero. The number of tilings of $H_{a,b,c}\setminus T$ is given by
	\vspace{-0.1cm}$$M(H_{a,b,c}\setminus T)=PP(a,b,c)\cdot|\det((P(a,b,c,l_j,r_i))_{1\le i,j\le k})|,\vspace{-0.1cm}$$
	where\footnote{Here the binomial function ${n}\choose{k}$ is defined as $n!/(k!(n-k)!)$ for $0\le k\le n$, and $0$ otherwise.}
	\vspace{-0.1cm}\begin{multline*}P(a,b,c,l_j,r_i):=\left[\binom{x(l_j)+y(l_j)-x(r_i)-y(r_i)}{x(l_j)-x(r_i)}-\sum_{t=0}^{a-1}\left(\left(\binom{c+t}{t}\binom{(b+c)+t}{b}\right)^{-1}\right.\right.\\\cdot\sum_{u=0}^{t}(-1)^u\binom{\tfrac{(b+c)}{2}-x(r_i)-y(r_i)}{\tfrac{(a+c)}{2}-x(r_i)-u-\tfrac{1}{2}}\binom{c+t-u-1}{c-1}\binom{b+u}{u}\\\left.\left.\cdot\sum_{v=0}^{t}(-1)^v\binom{\tfrac{(b+c)}{2}+x(l_j)+y(l_j)}{\tfrac{(a+b)}{2}+y(l_j)-v-\tfrac{1}{2}}\binom{b+t-v-1}{b-1}\binom{c+v}{v}\right)\right],\vspace{-0.1cm}\end{multline*}
	and $(x(l_j),y(l_j)),(x(r_i),y(r_i))$ are co-ordinates in $(\tfrac{1}{2}\mathbb{Z})^2$ determined by $l_j$ and $r_i$ respectively.\footnote{See \cref{rmk:Coords} in \cref{sec:NonInt}.} 
\end{thm}

\begin{rmk}\label{rmk:UseFull}
	The condition on $T$ is very general indeed, hence \cref{thm:MainRes} has a wide range of potential applications. For example $T$ may be the union of a set of unit rhombi, in which case the formula above gives the number of tilings of $H_{a,b,c}$ that contain a specified configuration of unit rhombi. Similarly if $T$ is a set of unit triangles on the outer boundary of $H_{a,b,c}$ then \cref{thm:MainRes} specialises to the generalised version of Kuo condensation for $H_{a,b,c}$ that may be found in~\cite{Ciucu15}.
\end{rmk}

The proof of the above theorem (see~\cite{Gilmore17}) involves merging two separate approaches to tiling enumeration. On one side we have a method due to Kasteleyn~\cite{Kasteleyn63,Kasteleyn67} (outlined in \cref{sec:KastMeth}) that considers tilings in their equivalent form as \emph{perfect matchings} (sometimes referred to as \emph{dimer coverings}) of sub-graphs of the hexagonal lattice $\mathscr{H}$. On the other we have the classic translation of tilings to \emph{non-intersecting lattice paths} for which there exists a well-known and celebrated determinant formula due to Lindstr\"om~\cite{Lindstrom73}, and Gessel and Viennot~\cite{GesselViennot89} (discussed in \cref{sec:NonInt}). In \cref{sec:TheUnion}, with the help of further results due to Cook and Nagel~\cite{CookNagel15} we marry together these inherently different approaches to determine the entries of the \emph{inverse Kasteleyn matrix} corresponding to $H_{a,b,c}$, from which \cref{thm:MainRes} follows. We conclude in \cref{sec:Conc} with a brief discussion of how \cref{thm:MainRes} could potentially lead to a proof of Ciucu's electrostatic conjecture~\cite{Ciucu08}.

\vspace{-0.4cm}\section{Kasteleyn's method}\label{sec:KastMeth}
Let us begin by considering the finite bipartite planar graph $G$ (embedded on a sphere) consisting of $2n$ black and white vertices labelled $b_1,b_2,\dots,b_n$ and $w_1,w_2,\dots,w_n$ respectively, where we have attached real-valued weights to the edges of $G$. A \emph{matching} of $G$ is a subset of edges that are non-adjacent (that is, no two edges contain a common vertex) and a \emph{perfect matching} (often referred to as a \emph{dimer covering}) of $G$ is a matching in which every vertex of $G$ is incident to precisely one edge.

 Given such a graph it is possible to form the \emph{weighted bi-adjacency matrix} corresponding to $G$ (denoted $A_G$), where $A_G=(w(b_i,w_j))_{1\le i,j\le n}$ is the $n\times n$ matrix with entries given by the sum of the weights of the edges between vertices $b_i$ and $w_j$. If the weight of a dimer covering is defined to be the product of the weights of the edges it consists of then the weighted count of dimer coverings of $G$ is given by
 \vspace{-0.1cm}\begin{equation}\label{eq:Perm}\sum_{\sigma\in \mathfrak{S}_n}\prod_{i=1}^nw(b_i,w_{\sigma(i)}),\vspace{-0.1cm}\end{equation}
 (here $\mathfrak{S}_n$ denotes the symmetric group on $n$ letters). The expression above is more succinctly described as the \emph{permanent} of $A_G$, denoted $\perm(A_G)$.
 
 If our goal is to count dimer coverings of $G$ one may be forgiven for thinking that this particular method could prove ineffective-- the permanent is, after all, a somewhat enigmatic function about which little is well understood. A great deal more is known about the determinant-- the much loved distant relative of~\eqref{eq:Perm}, which is far easier to compute and has a comparative abundance of useful properties. 
\vspace{-0.2cm}\subsection{Determining the permanent}\label{subsec:DetPerm}
How, then, may we relate the permanent of a matrix to its determinant? As far as the author is aware there exists no general method that allows us to express one in terms of the other, however Kasteleyn~\cite{Kasteleyn63,Kasteleyn67} showed that in certain situations the permanent of a matrix is equal to its determinant (up to sign).

First let us orient the surface of the sphere on which $G$ is embedded by endowing it with a sense of rotation in the clock-wise direction. Suppose we orient $G$ by directing each edge from a black vertex to a white one. Kasteleyn showed that it is possible to change the direction of a (possibly empty) set of edges so that in each oriented face of $G$, an odd number of edges agree with the orientation of the surface of the sphere (when the edges are viewed from the interior of each face). Such an orientation of $G$ is called \emph{admissible} and we encode it within the weighting by multiplying by $-1$ the weights of those edges that are directed from white to black. A weighting that encodes an admissible orientation is referred to as $flat$ by Kuperberg~\cite{Kuperberg94} and we denote the flat-weighted graph obtained from $G$ by $G_{\pm}$. If $A_{G_{\pm}}$ is the weighted bi-adjacency matrix corresponding to $G_{\pm}$ (often referred to as the \emph{Kasteleyn matrix} of $G_{\pm}$) then Kasteleyn showed that\vspace{-0.1cm}\begin{equation}
\label{eq:PermNDet}\perm(A_{G_{\pm}})=\pm\det(A_{G_{\pm}}).\vspace{-0.1cm}\end{equation}

The method described above may be applied to any planar bipartite graph $G$ (even more generally, the approach outlined in~\cite{Kasteleyn63,Kasteleyn67} is applicable to any planar graph embedded on the sphere). In particular, suppose $V$ is a subset of vertices of $G_{\pm}$ in which the black and white vertices are equinumerous, and let $G_{\pm}\setminus V$ denote the weighted sub-graph obtained by removing from $G_{\pm}$ the vertices contained in $V$ (together with all edges incident to them). The (signed) weights of the edges that remain in $G_{\pm}\setminus V$ are inherited from $G_{\pm}$, thus the bi-adjacency matrix corresponding to $G_{\pm}\setminus V$ (denoted $A_{G_{\pm}\setminus V}$) is the sub-matrix obtained from $A_{G_{\pm}}$ by deleting the rows and columns that are indexed by the vertices in $V$. If the inherited weighting of $G_{\pm}\setminus V$ is flat then it follows that $|\det (A_{G_{\pm}\setminus V})|$ gives the (weighted) count of the number of (weighted) dimer coverings of $G_{\pm}\setminus V$, thus a set of vertices for which this holds shall be deemed \emph{flatness-preserving}. If, on the other hand, the inherited weighting of $G_{\pm}\setminus V$ is not flat then $|\det (A_{G_{\pm}\setminus V})|$ gives instead the (weighted) count of the number of \emph{signed perfect matchings} of $G_{\pm}\setminus V$ (in the nomenclature of~\cite{CookNagel15}).
\begin{figure}
	\centering
	\includegraphics[width=0.65\textwidth]{HabcT}
	\caption{A tiling containing holes all of charge 2 (left) and its dual representation (right), where the flatness-preserving vertices are coloured red and the perfect matching is the set of solid lines.}
	\label{fig:TilG}
\vspace{-0.8cm}\end{figure}
\vspace{-0.2cm}\subsection{Kasteleyn's method applied to regions that contain holes}\label{subsec:KastHole}
Returning now to the hexagon $H_{a,b,c}$ defined in \cref{sec:Intro}, let $G_{a,b,c}$ denote the \emph{hexagonal sub-graph} obtained from $H_{a,b,c}$ by considering its dual\footnote{The graph $G_{a,b,c}$ is obtained by replacing left and right pointing unit triangles in $H_{a,b,c}$ with white and black vertices (respectively), where edges between vertices in $G_{a,b,c}$ correspond to edges between adjacent unit triangles in $H_{a,b,c}$} (see \cref{fig:TilG}). Clearly $G_{a,b,c}$ is a sub-region of $\mathscr{H}$ (the hexagonal lattice) that consists of a collection of hexagonal faces glued together. If we attach weights of $1$ to each edge then the number of dimer coverings of $G_{a,b,c}$, denoted $M(G_{a,b,c})$, is given by $\perm(A_{G})$ (where $A_{G}$ is the $(ab+bc+ca)\times(ab+bc+ca)$ bi-adjacency matrix corresponding to $G_{a,b,c}$).

Suppose the plane that contains the hexagonal lattice is endowed with a clock-wise rotation, and let us direct the edges of $G_{a,b,c}$ from black vertices to white (as in the previous section). It should be clear that in each oriented hexagonal face of $G_{a,b,c}$ the number of directed edges that are oriented clock-wise is odd (when the edges are viewed from the interior of each face). A straightforward argument shows that same is true for the outer boundary of $G_{a,b,c}$ (this is also a face), thus the orientation of $G_{a,b,c}$ is already admissible and it follows that $M(G_{a,b,c})=|\det(A_G)|$. Moreover, if $G_{a,b,c}\setminus V$ denotes the sub-graph obtained by removing from $G_{a,b,c}$ a set of flatness-preserving vertices $V=\{b_1,\dots,b_k,w_1,\dots,w_k\}$, then it follows that\vspace{-0.1cm}\begin{equation}\label{eq:AGE}M(G_{a,b,c}\setminus V)=|\det (A_{G\setminus V})|.\vspace{-0.1cm}\end{equation}
\begin{rmk}\label{rmk:FormalFP}The set of vertices $V$ is a union of \emph{unconnected subsets of vertices} where in each subset the vertices are \emph{connected via faces}, that is, $V:=\cup_{i}{V_i}$ where either $V_i$ consists of a single vertex, or for every $v\in V_i$ there exists at least one other vertex $v'\in V_i, v\neq v'$ that belongs to the same face as $v$, and no two vertices $v\in V_i,v'\in V_j$ are connected for $i\neq j$. It follows that $V$ is flatness-preserving if and only if the number of black vertices in each set $V_i$ is of the same parity as the number of white ones (see \cref{fig:TilG}, right).
\end{rmk} 

 
 So far we have established a method by which we may compute the number of dimer coverings of the holey hexagonal sub-graph $G_{a,b,c}\setminus V$ as the determinant of a matrix whose size is dependent on the number of vertices that are contained within the graph. Straightforward linear algebra, however, affords us an alternative way of evaluating the right hand side of~\eqref{eq:AGE} as a determinant of a matrix the size of which is dependent on the number of vertices that have been removed, instead of those that comprise $G_{a,b,c}\setminus V$. 
 
 If $(A_{G}^{-1})_{V}$ denotes the sub-matrix obtained by restricting the inverse of $A_{G}$ to the \emph{columns} indexed by $\{b_1,\dots,b_k\}\subset V$ and \emph{rows} indexed by $\{w_1,\dots,w_k\}\subset V$, then 
 \vspace{-0.1cm}\begin{equation}
 \label{eq:Keny1}
|\det(A_{G\setminus V})|=|\det(A_G)\cdot\det((A_{G}^{-1})_{V})| \vspace{-0.1cm}\end{equation}
 (it should be noted that the above formula does not depend on whether $V$ is a flatness-preserving set of vertices). The determinant $|\det(A_G)|$ is the number of dimer coverings of $G_{a,b,c}$ (equivalently, tilings of $H_{a,b,c}$), given by MacMahon~\cite{MacMahon16} and discussed in \cref{sec:Intro}. It therefore follows that
 \vspace{-0.1cm}\begin{equation}
 \label{eq:Keny2}M(G_{a,b,c}\setminus V)=PP(a,b,c)\cdot|\det((A_{G}^{-1})_{V})|,\vspace{-0.1cm}\end{equation}
and what remains is to determine the individual entries of the \emph{inverse Kasteleyn matrix} $A_{G}^{-1}$.

The $(i,j)$-entry of $A_{G}^{-1}$ is
\vspace{-0.1cm}$$(-1)^{i+j}\cdot\det(A_{G\setminus V_{j,i}})(\det (A_G))^{-1},\vspace{-0.1cm}$$
where $A_{G\setminus V_{j,i}}$ is the sub-matrix obtained by deleting row $j$ and column $i$ from $A_{G}$. If the pair of vertices $V_{j,i}=\{b_j,w_i\}$ are flatness-preserving then the determinant of $A_{G\setminus V_{j,i}}$ is simply $\pm$ the number of dimer coverings of the graph $G_{a,b,c}\setminus V_{j,i}$, otherwise it gives $\pm$ the number of signed perfect matchings of $G_{a,b,c}\setminus V_{j,i}$. Such matchings may be interpreted as dimer coverings of $G_{a,b,c}\setminus V_{j,i}$ where the edges around the hole(s) created by the removal of the vertices $b_j,w_i$ have a certain weighting that does not correspond to an admissible orientation.

If we stay within $\mathscr{H}$, considering dimer coverings of $G_{a,b,c}\setminus V$, then the way forward appears somewhat murky; the $(i,j)$-entries of $(A_G^{-1})_{V}$ may be interpreted as (signed) perfect matchings in which the edge weights are \emph{locally} dependent on the vertices $b_j$ and $w_i$ that have been removed. We shall see in the next section, however, that by switching our perspective from $\mathscr{H}$ back to $\mathscr{T}$, this sensitive local dependence of edge weights in signed perfect matchings is captured \emph{globally} by applying the theorem of Lindstr\"{o}m~\cite{Lindstrom73}, and Gessel and Viennot~\cite{GesselViennot89} to count certain families of non-intersecting lattice paths.

\vspace{-0.2cm}\section{Non-intersecting lattice paths}\label{sec:NonInt}
We now return to $\mathscr{T}$, thus if $G_{a,b,c}\setminus V$ is a hexagonal sub-graph of $\mathscr{H}$ where $V=\{b,w\}$ then we consider its dual, the hexagonal sub-region $H_{a,b,c}\setminus T$ of $\mathscr{T}$, where $T=\{l,r\}$ is a pair of unit triangles (one left pointing, $l$, one right pointing, $r$) corresponding to $w$ and $b$ in $G_{a,b,c}$ (respectively). Within this setting, if $V$ is a flatness-preserving set of vertices then $l$ and $r$ are connected.  
\begin{rmk}\label{rmk:VnT}
	More generally, if $V:=\cup_iV_i$ is a union of unconnected sets of connected vertices on $\mathscr{H}$ then each $V_i$ corresponds to a set $T_i$ of connected unit triangles that comprise a region on $\mathscr{T}$, and the $T_i$'s are unconnected. It follows from the observation in \cref{rmk:FormalFP} that if $V$ is flatness-preserving then the charge of each $T_i\in T$ must be even. Throughout this section, however, we shall assume that $T$ is simply a pair of unit triangles and $V$ a pair of vertices.
\end{rmk}
\begin{figure}
	\centering
	\includegraphics[width=1\textwidth]{fig4}
	\caption{Two tilings of a holey hexagon (left and centre right) that are represented by families of non-intersecting lattice paths that arise from distinct permutations mapping start points to end points.}
	\label{fig:famBij}
\vspace{-0.8cm}\end{figure}
\vspace{-0.2cm}\subsection{A classical bijection}
A bijection exists within the folklore of plane partitions and tilings that allows one to represent tilings of $H_{a,b,c}\setminus T$ as families of non-intersecting paths consisting of unit north and east steps on the half-integer lattice\footnote{A family of lattice paths $\mathcal{P}$ is non-intersecting if no two distinct paths in $\mathcal{P}$ meet at a lattice point.}. Given a tiling of $H_{a,b,c}\setminus T$, place a set of $a$-many start (end, respectively) points so that each point lies in the middle of the south-west (north-east) edge of the unit rhombi that lie along the south-west (north-east) boundary of $H_{a,b,c}\setminus T$. Place one further start (end, respectively) point at the mid-point of the north-east (south-west) edge of the right (left) pointing unit triangle $r$ ($l$). Denote by $S_{\mathscr{T}}$ and $E_{\mathscr{T}}$ these sets of $(a+1)$ start and end points (respectively) that lie on the edges of the hexagon and any holes in its interior.

Beginning at a point in $S_{\mathscr{T}}$ we may construct a \emph{path across unit rhombi} by travelling from the mid-point of one side of each unit rhombus to the mid-point of its opposite parallel side. If we apply this process to every point in $S_{\mathscr{T}}$ we obtain a \emph{family of paths across unit rhombi} that end at the set of points $E_{\mathscr{T}}$, where no two paths traverse the same unit rhombus (see \cref{fig:famBij}).

We may easily translate this set of paths into a \emph{family of non-intersecting lattice paths} consisting of north and east unit steps that begin at the tuple of points $S:=(s_1,\dots,s_{a+1})$, where $s_i:=(\frac{a-c+1}{2}-i,i-\frac{a+b+1}{2})$ for $i\in\{1,\dots,a\}$ and $s_{a+1}:=(x(r),y(r))$, and end at the tuple of points $E:=(e_1,\dots, e_{a+1})$, where $e_j:=(\frac{a+c+1}{2}-j,j+\frac{b-a-1}{2})$ for $j\in\{1,\dots,a\}$ and $e_{a+1}:=(x(l),y(l))$ (see \cref{fig:famBij}, right and centre-left). Note that the first co-ordinate of each point is an integer if $a$ and $c$  differ in parity, and a half integer otherwise. A similar condition holds for the second co-ordinate.
\begin{rmk}\label{rmk:Coords}
The start and end points $s_{a+1}$ and $e_{a+1}$ are given by the co-ordinate positions of the triangles $l$ and $r$ when tilings of $H_{a,b,c}\setminus\{l,r\}$ are translated into families of non-intersecting lattice paths. Throughout this article we will associate with the triangles $l$ and $r$ two pairs of co-ordinates $(x(l),y(l))$, $(x(r),y(r))$ respectively, where $x$ and $y$ are functions that map unit triangles to half integers, so $(x(*),y(*))\in(\tfrac{1}{2}\mathbb{Z})^2$. The precise way in which these co-ordinates are obtained is described in~\cite[Section~3]{Gilmore17}.
\end{rmk}
\vspace{-0.2cm}\subsection{Not exactly enumerating families of non-intersecting lattice paths}
Translating tilings into families of non-intersecting paths is often extremely beneficial since there is a theorem due to Lindstr\"om~\cite{Lindstrom73}, and Gessel and Viennot~\cite{GesselViennot89} that allows one to express a sum of signed numbers of families non-intersecting paths as a certain determinant.

For a permutation $\sigma\in\mathfrak{S}_{a+1}$ mapping the set of start points $S$ to the set of end points $E_{\sigma}:=(e_{\sigma(1)},e_{\sigma(2)},\dots,e_{\sigma(a+1)})$, let $N(S,E_{\sigma})$ denote the number of families of non-intersecting paths that arise from this mapping. The number of \emph{signed families of lattice paths} from $S$ to $E$ (equivalently, \emph{signed lozenge tilings} of $H_{a,b,c}\setminus T$) is given by
\vspace{-0.1cm}\begin{equation}
\label{eq:signedSum}\left|\sum_{\sigma\in\mathfrak{S}_{a+1}}\sgn(\sigma)N(S,E_{\sigma})\right|.
\vspace{-0.1cm}\end{equation}

According to~\cite{GesselViennot89,Lindstrom73} the expression above may be written as a determinant, that is,
\vspace{-0.1cm}\begin{equation}
\label{eq:SignedPaths}
\sum_{\sigma\in\mathfrak{S}_{a+1}}\sgn(\sigma)N(S,E_{\sigma})=\pm\det (P_{H\setminus T}),\vspace{-0.1cm}\end{equation}
where $P_{H\setminus T}:=(\mathscr{P}(s_i\to e_{j}))_{1\le i,j\le a+1}$ is the \emph{lattice path matrix} with $(i,j)$-entry given by the number of paths from the start point $s_i\in S$ to the end point $e_j\in E$.

\begin{prop}\label{prop:FirstProp}
	The number of signed tilings of $H_{a.b.c}\setminus T$ is given by $|\det(P_{H\setminus T})|$, where $P_{H\setminus T}=(P_{i,j})_{1\le i,j\le a+1}$ has entries given by
	\vspace{-0.1cm}$$P_{i,j}=\begin{cases}\binom{b+c}{c+i-j}& 1\le i,j\le a,\\
	\binom{x(l)+y(l)+b/2+c/2}{x(l)+i-a/2+c/2-1/2}& 1\le i\le a, j=a+1,\\
	\binom{b/2+c/2-x(r)-y(r)}{a/2+c/2+1/2-j-x(r)}& i=a+1,1\le j\le a,\\
	\binom{x(l)+y(l)-x(r)-y(r)}{x(l)-x(r)}& i=j=a+1.\end{cases}\vspace{-0.1cm}$$
	\end{prop}

When faced with such a determinant there are a host of useful tools and tricks one may employ in order to try to establish its evaluation explicitly (the approach used in~\cite{Gilmore17} is similar to that of~\cite{Gilmore16}). By guessing the entries of the $LU$-decomposition of $P_{H\setminus T}$ with software such as {\tt Rate}\footnote{A guessing machine created by C.~Krattenthaler, available at~\url{http://www.mat.univie.ac.at/~kratt/rate/rate.html}.} and using your favourite computer implementation of Zeilberger's algorithm (see~\cite{PauleSchorn95}, for example) to verify the decomposition is correct, it is possible to deduce the following theorem.
\begin{thm}\label{thm:det}
	The determinant of $P_{H\setminus T}$ is equal to $PP(a,b,c)\cdot P(a,b,c,l,r)$.	
\end{thm}

\vspace{-0.2cm}\section{The holey union}\label{sec:TheUnion}
We now describe how to relate the determinant of $P_{H\setminus T}$ with that of $A_{G\setminus V}$. We do this by examining more closely the terms in the expressions that count signed lozenge tilings of $H_{a,b,c}\setminus T$ and signed perfect matchings of $G_{a,b,c}\setminus V$.
Suppose $V=\{b,w\}$ is a set of any two vertices in the interior of $G_{a,b,c}$. As discussed in \cref{sec:KastMeth}, the number of signed perfect matchings of $G_{a,b,c}\setminus V$ is given (up to sign) by
\vspace{-0.1cm}\begin{equation}
\label{eq:SignPerf}\sum_{\pi\in\mathfrak{S}_{ab+bc+ca-1}}\sgn(\pi)\prod_{i=1}^{ab+bc+ca-1}(A_{G\setminus V})_{i,\pi(i)},
\vspace{-0.1cm}\end{equation}
thus if we were to expand out the above sum we could partition the matchings of $G_{a,b,c}\setminus V$ into those that contribute positively to the sum, $M^+$, and those that contribute negatively, $M^-$. 

Similarly if $T=\{l,r\}$ is the pair of unit triangles on $\mathscr{T}$ corresponding to the vertices $V$ on $\mathscr{H}$, then in the same way we could also re-arrange~\eqref{eq:signedSum} and thus partition rhombus tilings of $H_{a,b,c}\setminus T$ into those that contribute positively to~\eqref{eq:signedSum}, $P^+$, and those that contribute negatively, $P^-$.

In 2015 Cook and Nagel~\cite{CookNagel15} showed that for regions that are more general\footnote{In~\cite{CookNagel15} they consider large triangular regions of $\mathscr{T}$, but these may be specialised to the hexagons with which we are concerned by cutting off their corners.} than the hexagons considered here, the tilings that are contained in $P^+$ are precisely the rhombus tiling representations of \emph{either} those matchings in $M^+$, \emph{or} the ones in $M^-$, thus
\vspace{-0.1cm}$$\det(A_{G\setminus V})=\pm\det(P_{H\setminus T}).\vspace{-0.1cm}$$

Note that in expressing the signed lozenge tilings as a determinant we have fixed a labelling of the start and end points for all holey hexagons. Thus if we suppose the vertices of $G_{a,b,c}$ also have a fixed labelling then for any two pairs of vertices this discrepancy will be consistent\footnote{That is, if  $V,V'$ are two distinct pairs of vertices in $G_{a,b,c}$, each pair consisting of one white and one black vertex, and $T,T'$ are the corresponding pairs of unit triangles in $H_{a,b,c}$, then either $\det(A_{G\setminus V})=-\det(P_{H\setminus T})$ and $\det(A_{G\setminus V'})=-\det(P_{H\setminus T'})$, or $\det(A_{G\setminus V})=\det(P_{H\setminus T})$ and $\det(A_{G\setminus V'})=\det(P_{H\setminus T'})$.} for all pairs of vertices in $G_{a,b,c}$. Combining this fact with \cref{thm:det} gives rise to the following corollary.
\begin{cor}
	Suppose $G_{a,b,c}$ is the hexagonal sub-region of $\mathscr{H}$ with all edge weights set to 1. If $A_G$ is the bi-adjacency matrix of $G_{a,b,c}$ then  \vspace{-0.1cm}$$A_{G}^{-1}=(\pm1)\cdot((-1)^{(i+j)}P(a,b,c,l_j,r_i))_{1\le i,j\le ab+bc+ca}.\vspace{-0.1cm}$$
\end{cor}
 The proof of \cref{thm:MainRes} follows from combining the above corollary with equations~\eqref{eq:Keny1} and~\eqref{eq:Keny2} in \cref{subsec:KastHole}.

\vspace{-0.2cm}\section{Not quite happily ever after}\label{sec:Conc}
\cref{thm:MainRes} is a very general result that allows us to compute the number of tilings of a hexagon containing a set of holes of any size and shape, located anywhere within its interior, so long as each hole has an even charge and the sum of the charges of the holes is 0. Moreover it affords us a new perspective from which we may consider the "effect" that such a set of holes has on tilings of the entire plane.

Suppose $T$ is a set of holes contained within $H_{an,bn,cn}$ of fixed size, with their positions fixed with respect to the centre of $H_{an,bn,cn}$. The \emph{correlation function} (or \emph{interaction}) of the holes is given by 
\vspace{-0.1cm}$$\omega(T):=\lim_{n\to\infty}\frac{M(H_{an,bn,cn}\setminus T)}{M(H_{an,bn,cn})},\vspace{-0.1cm}$$
thus as $n\to\infty$ this function describes the interaction between the holes within a \emph{sea of unit rhombi}.

\begin{conj*}[Ciucu '08]
	Let $T$ be any set of holes of fixed size and position in the plane, where the distance between holes is proportional to $k$. Then $\omega(T)/I(T)\to1$ as $k\to\infty$, where
	\vspace{-0.1cm}$$I(T):=\prod_{t\in T}C_t\prod_{1\le i< j\le |T|}d(t_i,t_j)^{\frac{1}{2}q(t_i)q(t_j)},\vspace{-0.1cm}$$
	in which $C_t$ is some constant dependent on each hole $t\in T$, $d(t_i,t_j)$ is the Euclidean distance between the holes $t_i$ and $t_j$, and $q(t_i)$ is the charge of the hole $t_i$.
\end{conj*}

As far as the author is aware this conjecture remains wide open. There exists a fairly general proof for tilings around holes that have been embedded on the torus~\cite{Ciucu09}, and similarly a  number of proofs already exist for specific types of holes in the plane (see~\cite{Gilmore16}). However if the asymptotic behaviour of the determinant expression in \cref{thm:MainRes} could be successfully shown to agree with the function $I(T)$ above then we would have a proof of Ciucu's conjecture for an incredibly general class of holes. This is apparently far easier said than done-- the asymptotics of the triple sum in $P(an,bn,cn,l,r)$ appear to be very tricky indeed to pin down.


\begingroup\emergencystretch=.5em
\printbibliography
\endgroup




\end{document}
